package clue.players2.ai;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

import org.javatuples.Triplet;

import clue.EnumerationEngine2;
import clue.board.Path;
import clue.board.Square;
import clue.cards.Card;
import clue.cards.RoomCard;
import clue.cards.SuspectCard;
import clue.cards.WeaponCard;
import clue.engine2.GameState2;
import clue.enums.Room;
import clue.enums.Suspect;
import clue.enums.Weapon;
import clue.players2.Player2;

public class MarkovAIPlayer extends Player2 {
	private EnumerationEngine2 engine;
	private HashMap<Integer, Integer> IDToOpponentIdx;
	private HashSet<Square> trace;
	private Room lastRoom;
	public int id;
	MarkovState[][][] states;
	HashMap<MarkovState, List<MarkovState>> actions;

	@Override
	public void gameStarted(GameState2 gs) {

		Card[] cards = new Card[gs.getOwnHand(this).size()];
		gs.getOwnHand(this).toArray(cards);
		engine = new EnumerationEngine2(gs.playerIDs.size(), cards);
		IDToOpponentIdx = new HashMap<>();
		int myID = gs.getOwnID(this);
		id = myID;
		List<Integer> ids = gs.playerIDs;
		int i;
		for (i = 0; i < ids.size(); i++) {
			if (ids.get(i) == myID)
				break;
		}
		int index = 0;
		for (int j = (i + 1) % ids.size(); j != i; j = (j + 1) % ids.size(), index++) {
			IDToOpponentIdx.put(ids.get(j), index);
		}
		trace = new HashSet<>();
		// For each state s, we make 7 markov states -> 0, 1, 2, 3, 4, 5, 6.
		// The 0 state corresponds to the state before the dice roll, and
		// 1-6 states correspond to the states after dice roll.

		// Since the geometry of the board remains static, we only have to do
		// this once.
		states = new MarkovState[gs.board.rows][gs.board.cols][7];
		actions = new HashMap<>();
		for (i = 0; i < gs.board.rows; i++) {
			for (int j = 0; j < gs.board.cols; j++) {
				Square s = gs.board.board[i][j];
				for (int k = 0; k < 7; k++) {
					states[i][j][k] = new MarkovState(s, k);
					actions.put(states[i][j][k], new LinkedList<MarkovState>());
					if (k > 0) {
						// This means a pre-dice state can get to any of the 6
						// post-dice states. Note that we implicitly assume
						// the probability of transition is 1/6.
						actions.get(states[i][j][0]).add(states[i][j][k]);
					}
				}

			}
		}

		// Second pass -- we perform a BFS to set the actions according to
		// the structure of the connectivity graph. We need this second pass
		// because otherwise not all MarkovStates have been instantiated.

		for (i = 0; i < gs.board.rows; i++) {
			for (int j = 0; j < gs.board.cols; j++) {
				BfsSetProb(gs.board.board[i][j]);
			}
		}
	}

	private Stack<Square> BFS(Square start, Square end) {
		Stack<Square> stack = null;
		Queue<Square> queue = new LinkedList<>();
		HashSet<Square> visited = new HashSet<>();
		HashMap<Square, Square> parent = new HashMap<>();
		queue.add(start);
		visited.add(start);
		while (!queue.isEmpty()) {
			Square s = queue.remove();
			// System.out.printf("(%d, %d) room = %s\n", s.x, s.y, s.room);
			if (end.equals(s)) {
				stack = new Stack<>();
				stack.push(s);
				while (parent.get(s) != null) {
					s = parent.get(s);
					// System.out.printf("(%d, %d) room = %s\n", s.x, s.y,
					// s.room);
					stack.push(s);
				}
				stack.pop();
				break;
			}
			for (Square t : s.neighbors) {
				if (!visited.contains(t)) {
					if (end.room != null && t.room != null
							&& !end.room.equals(t.room))
						continue;
					if (end.room == null && t.room != null
							&& t.room.equals(lastRoom))
						continue;
					queue.add(t);
					parent.put(t, s);
					visited.add(t);
				}
			}
		}
		return stack;
	}

	private class MarkovState {
		Square s;
		int dice;

		MarkovState(Square s, int dice) {
			this.s = s;
			this.dice = dice;
		}
	}

	private void BfsSetProb(Square s) {
		int maxDepth = 6;
		Map<Square, Integer> depthMap = new HashMap<>();
		Set<Square> visited = new HashSet<>();
		Queue<Square> queue = new LinkedList<>();

		queue.add(s);
		visited.add(s);
		depthMap.put(s, 0);

		while (!queue.isEmpty()) {
			Square cur = queue.remove();
			int depth = depthMap.get(cur);
			if (depth > maxDepth)
				continue;

			if (depth > 0) {
				for (int d = depth; d <= 6; d++) {
					// MarkovState(s,d) --> MarkovState(cur,0) with prob 1
					actions.get(states[s.x][s.y][d]).add(
							states[cur.x][cur.y][0]);
				}
			}

			for (Square n : cur.neighbors) {
				if (!visited.contains(n)) {
					visited.add(n);
					depthMap.put(n, depth + 1);
					queue.add(n);
				}
			}
		}
	}

	public double gamma = 0.7;
	public double epsilon = 0.0001;

	@Override
	public Path move(GameState2 gs, int dice) {
		HashMap<MarkovState, Double> V = new HashMap<>();
		// value iteration

		double[] maxProbs = new double[9];
		double[] R = new double[9];
		double maxProb = -1;
		for (int r = 0; r < 9; r++) {
			for (int s = 0; s < 6; s++) {
				for (int w = 0; w < 6; w++) {
					maxProb = Math.max(maxProb, engine.envProb[w][s][r]);
					maxProbs[r] = Math
							.max(maxProbs[r], engine.envProb[w][s][r]);
				}
			}
		}

		for (int r = 0; r < 9; r++) {
			R[r] = maxProbs[r] / maxProb;
		}

		double maxDelta = 0;
		do {
			for (int i = 0; i < gs.board.rows; i++) {
				for (int j = 0; j < gs.board.cols; j++) {
					for (int k = 0; k < 7; k++) {
						MarkovState s = states[i][j][k];
						double oldSV = V.containsKey(s) ? V.get(s) : 0;
						double sV = 0;
						if (k == 0) {
							// we know exactly how many s' there are -- 6
							// the reward for each is 0, because going from
							// regular state -> satellite state costs 0 and we
							// gain nothing because we haven't moved yet. We
							// only
							// rolled the dice.
							for (MarkovState sp : actions.get(s)) {
								double spV = V.containsKey(sp) ? V.get(sp) : 0;
								sV += gamma * spV / 6;
							}

						} else {
							// Each of these actions has a single state s',
							// and thus the transition probability is 1 for each
							double maxV = Double.NEGATIVE_INFINITY;
							for (MarkovState sp : actions.get(s)) {
								double spV = V.containsKey(sp) ? V.get(sp) : 0;
								double spR = -1
										+ (sp.s.room == null ? 0
												: (sp.s.room == lastRoom ? -10000
														: R[sp.s.room.ordinal()]));
								maxV = Math.max(maxV, spR + gamma * spV);
							}
							sV = maxV;
						}
						V.put(s, sV);
						maxDelta = Math.max(maxDelta, Math.abs(sV - oldSV));
					}
				}
			}
		} while (maxDelta > epsilon);

		// We simply need to get the best policy for our current situation:
		Square curSquare = gs.IDToSquare.get(gs.getOwnID(this));
		MarkovState curState = states[curSquare.x][curSquare.y][dice];
		double maxV = Double.NEGATIVE_INFINITY;
		MarkovState bestPolicy = null;
		for (MarkovState sp : actions.get(curState)) {
			double v = V.get(sp);
			if (v > maxV) {
				maxV = v;
				bestPolicy = sp;
			}
		}
		// System.out.println("MaxV = " + maxV);

		Stack<Square> stack = BFS(curSquare, bestPolicy.s);
		Path p = new Path();
		int count = 0;
		while (!stack.isEmpty()) {
			if (count == dice)
				break;
			Square s = stack.pop();
			if (trace.contains(s)) {
				System.out.println("Retracing old steps...");
			}
			trace.add(s);
			p.addSquare(s);

			if (s.room != null)
				break;
			count++;
		}
		return p;
	}

	@Override
	public Triplet<Room, Suspect, Weapon> suggest(GameState2 gs) {
		lastRoom = gs.IDToLocation.get((gs.getOwnID(this)));
		trace = new HashSet<>();
		double maxProbForUs = -1;
		int suspect = -1, weapon = -1;
		int ourR = lastRoom.ordinal();
		for (int s = 0; s < 6; s++) {
			for (int w = 0; w < 6; w++) {
				if (engine.envProb[w][s][ourR] > maxProbForUs) {
					maxProbForUs = engine.envProb[w][s][ourR];
					suspect = s;
					weapon = w;
				}
			}
		}
		return new Triplet<Room, Suspect, Weapon>(lastRoom,
				Suspect.values()[suspect], Weapon.values()[weapon]);
	}

	@Override
	public Card refute(GameState2 gs, Integer suggestingPlayerID,
			Triplet<Room, Suspect, Weapon> suggestion) {
		for (Card c : gs.getOwnHand(this)) {
			if (c instanceof RoomCard) {
				RoomCard rc = (RoomCard) c;
				if (rc.getRoom().equals(suggestion.getValue0()))
					return rc;
			} else if (c instanceof SuspectCard) {
				SuspectCard sc = (SuspectCard) c;
				if (sc.getSuspect().equals(suggestion.getValue1()))
					return sc;
			} else if (c instanceof WeaponCard) {
				WeaponCard wc = (WeaponCard) c;
				if (wc.getWeapon().equals(suggestion.getValue2()))
					return wc;
			}
		}
		return null;
	}

	@Override
	public void informMove(GameState2 gs, Integer movingPlayerID, Square s) {
		// TODO Auto-generated method stub

	}

	@Override
	public void informSuggestion(GameState2 gs, Integer suggestingPlayerID,
			Triplet<Room, Suspect, Weapon> suggestion) {
		/*
		 * engine.mustNotExist(new Card[] { new
		 * RoomCard(suggestion.getValue0()), new
		 * SuspectCard(suggestion.getValue1()), new
		 * WeaponCard(suggestion.getValue2()) },
		 * this.IDToOpponentIdx.get(suggestingPlayerID));
		 */
	}

	@Override
	public void informFailureToRefute(GameState2 gs, Integer failedPlayerID,
			Triplet<Room, Suspect, Weapon> suggestion) {
		engine.mustNotExist(new Card[] { new RoomCard(suggestion.getValue0()),
				new SuspectCard(suggestion.getValue1()),
				new WeaponCard(suggestion.getValue2()) },
				this.IDToOpponentIdx.get(failedPlayerID));
	}

	@Override
	public void informRefutation(GameState2 gs, Integer refutingPlayerID,
			Card refutingCard) {
		engine.mustExist(refutingCard,
				this.IDToOpponentIdx.get(refutingPlayerID));
	}

	@Override
	public void informRefutationHidden(GameState2 gs, Integer refutingPlayerID,
			Integer suggestingPlayerID,
			Triplet<Room, Suspect, Weapon> suggestion) {
		engine.opponentReaction(
				new Card[] { new RoomCard(suggestion.getValue0()),
						new SuspectCard(suggestion.getValue1()),
						new WeaponCard(suggestion.getValue2()) },
				this.IDToOpponentIdx.get(refutingPlayerID), true);
	}

	@Override
	public void gameEnded(GameState2 gs, Integer winnerID,
			Triplet<Room, Suspect, Weapon> winningAccusation) {
		// TODO Auto-generated method stub
		// if (gs.getOwnID(this) == winnerID)
		// System.out.println("StrongAIPlayer won!");
	}

	@Override
	public void informFailedAccusation(GameState2 gs, Integer failedPlayerID,
			Triplet<Room, Suspect, Weapon> failedAccusation) {
		// TODO Auto-generated method stub

	}

	@Override
	public Triplet<Room, Suspect, Weapon> accuse(GameState2 gs) {
		for (int r = 0; r < 9; r++) {
			for (int s = 0; s < 6; s++)
				for (int w = 0; w < 6; w++) {
					if (engine.envProb[w][s][r] > 0.95)
						return new Triplet<Room, Suspect, Weapon>(
								Room.values()[r], Suspect.values()[s],
								Weapon.values()[w]);
				}
		}
		return null;
	}

}
